package tanxin;

/**
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * 假设你总是可以到达数组的最后一个位置。
 *
 */
public class leetCode45_jump {
    public int jump(int[] nums) {
        int end = 0; // 一次跳跃后的边界
        int maxLength = 0;
        int step = 0;

        // 因为要算出最小值，所以要遍历到底
        // 下标i到达nums.length - 1就已经结束了，所以没必要遍历到nums.length - 1
        for (int i = 0; i < nums.length - 1; i++) {
            maxLength = Math.max(maxLength,nums[i] + i);
            // 这个过程可以理解为，取在一个边界内的最大值
            if(i == end){
                end = maxLength;
                step++;
            }
        }
        return step;
    }


    public int jump2(int[] nums) {
        int end = 0;
        int maxLength = 0;
        int step = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            maxLength = Math.max(maxLength,nums[i] + i);
            if(i == end){
                end = maxLength;
                step++;
            }
        }
        return step;



    }
}
